design characteristic-2

Status: accepted (2026-11-19, maintainer). Elements of are nimbers by default; Conway polynomials are the secondary representation and the default for every other 𝑛; the cryptographers’ polynomials (AES, GHASH, …) are alternatives for cryptanalysis and interoperability.

Code: julia/FiniteFieldArithmetic.jl/src/nimber.jl (and its note nimber.md). Backlog: J1a, J1b, J7, V6.

Context

A field has many concrete representations, one per choice of basis; the usual one is a polynomial basis modulo an irreducible polynomial of degree 𝑛. The maintainer asked for the choice that gives the most structure, especially across several fields, rather than a polynomial picked by cryptographers for cheap reduction. The project’s purpose (general theory, cryptanalysis, learners built on finite fields) favours structure and bulk arithmetic over interoperability.

Options considered

  1. Conway polynomials 𝐢𝑛, for every 𝑛: the lexicographically least monic primitive polynomial of degree 𝑛 over compatible with πΆπ‘š for all , i.e. . Then the embeddings , , commute. Categorically: finite fields of characteristic 2 have π‘š embeddings when (one per Galois automorphism); Conway polynomials choose one coherently, a functor from the divisibility poset into fields whose colimit is a concrete . Since is primitive, discrete logarithms are compatible as well. Costs: β€œleast” is a convention (the compatibility is the structure); the tables (LΓΌbeck) end at some degree, beyond which pseudo-Conway polynomials (compatible, not minimal) must be computed; they are dense, so reduction is slower than with a trinomial.
  2. Nimbers (Conway, On Numbers and Games, ch. 6), for 𝑛=2π‘˜: the integers below 2{2π‘˜} with XOR and nim-multiplication form , and these fields are nested as sets of integers. The embedding keeps the bit pattern; no polynomial is chosen at all (each level is the Artin–Schreier extension by a root of 𝑋2+𝑋+𝐹2 of the one below). The union is the quadratic closure of , and levels 3–7 are exactly the byte-sized fields of 8–128 bits, the maintainer’s priority. Lean: the CombinatorialGames project defines Nimber (on our toolchain v4.36.0); mathlib v4.36.0 has neither nimbers nor Conway polynomials. Cost: no hardware instruction like carry-less multiplication helps; the large levels must be benchmarked against polynomial bases.
  3. Standard low-weight polynomials (AES π‘₯8+π‘₯4+π‘₯3+π‘₯+1, GHASH π‘₯{128}+π‘₯7+π‘₯2+π‘₯+1): fast reduction and interoperability with existing software; no structure across fields.

Decision

Nimbers for 𝑛=2π‘˜, Conway polynomials (pseudo-Conway beyond the tables) for other 𝑛 and for , standard polynomials as alternatives. A change of representation is an -linear map (an bit matrix), cheap in bulk.

Consequences

  • Subfield arithmetic is free in the nimber representation: GF(16) values are GF(256) values, so mixed-level arithmetic is promotion, and one set of GF(256) tables serves every level up to it (measured: nimber.md).
  • Conversions between representations must be explicit (no implicit isomorphism); elements of different representations compare unequal.
  • Fields that are not of the form 2{2π‘˜} (e.g. ) wait for the Conway representation (J1b).